import java.util.*;

//public class Solution {
//    public int numJewelsInStones(String jewels, String stones) {
//        Set<Character> set = new HashSet<>();
//        //存宝石
//        for (int  i = 0; i < jewels.length(); i++) {
//            char ch = jewels.charAt(i);
//            set.add(ch);
//        }
//        //判断石头
//        int count = 0;
//        for (int i = 0; i < stones.length(); i++) {
//            char ch = stones.charAt(i);
//            if(set.contains(ch)){
//                count++;
//            }
//        }
//        return count;
//    }
//}

//
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//class Solution {
//    public Node copyRandomList(Node head) {
//    Node cur = head;
//    HashMap<Node,Node> map = new HashMap<>();
//    //存新旧结点
//    while (cur != null){
//        Node node = new Node(cur.val);
//        map.put(cur,node);
//        cur = cur.next;
//    }
//    cur = head;
//    while (cur != null){
//        map.get(cur).next = map.get(cur.next);
//        map.get(cur).random = map.get(cur.random);
//        cur = cur.next;
//    }
//    return map.get(head);
//    }
//}

//class Solution {
//    public boolean containsDuplicate(int[] nums) {
//        Set<Integer> set = new HashSet<>();
//        for (int i = 0; i < nums.length; i++) {
//            if (set.contains(nums[i])) {
//                return true;
//            }else{
//                set.add(nums[i]);
//            }
//        }
//        return false;
//    }
//}

//class Solution {
//    public boolean containsNearbyDuplicate(int[] nums, int k) {
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            if(map.containsValue(nums[i]) && i - map.get(nums[i]) <= k){
//                return true;
//            }else{
//                map.put(nums[i],i);
//            }
//        }
//        return false;
//    }
//}

//class Solution {
//    public int singleNumber(int[] nums) {
//        int ret = nums[0];
//        for (int i = 1; i < nums.length; i++) {
//            ret = ret ^ i;
//        }
//        return ret;
//    }
//}


class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //存数据
        Map<String,Integer> map = new HashMap<>();
        for(String word: words){
            if (map.get(word) == null){
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //设置小根堆的比较器
        PriorityQueue<Map.Entry<String,Integer>> minheap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                 if(o1.getValue().compareTo(o2.getValue()) == 0){
                     return o2.getKey().compareTo(o1.getKey());
                 }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String,Integer> entry : map.entrySet()){
            if (minheap.size() < k){
                minheap.offer(entry);
            }else{
                Map.Entry<String,Integer> top = minheap.peek();
                if(entry.getValue().compareTo(top.getValue()) > 0){
                    minheap.poll();
                    minheap.offer(entry);
                } else if (entry.getValue().compareTo(top.getValue()) == 0) {
                    if (entry.getKey().compareTo(top.getKey()) < 0){
                        minheap.poll();
                        minheap.offer(entry);
                    }
                }
            }
        }
        //取数据放到列表中
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp = minheap.poll();
            list.add(tmp.getKey());
        }
        //逆置
        Collections.reverse(list);
        return list;
    }
}